package org.hhchat.leetcode.banarySearch;

/**
 * Created this one by HMH on 2017/9/30.
 */
public class code367_easy {

    static class Solution {
        public boolean isPerfectSquare(int num) {
            System.out.println(sqrt(num));
            int n = sqrt(num);
            return n * n == num;
        }

        public int sqrt(int n) {
            if (n == 0 || n == 1) {
                return n;
            }
            int mid,left = 1, right = n;
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (mid > n / mid) {
                    right = mid - 1;
                } else if (mid == n / mid) {
                    return mid;
                } else {
                    if ((mid + 1) > n / (mid + 1)) {
                        return mid;
                    }
//                    if ((mid + 1) == n / (mid + 1)) {
//                        return mid + 1;
//                    }
                    left = mid + 1;
                }
            }
            return (left + right) / 2;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.isPerfectSquare(9));
    }
}

//    public boolean isPerfectSquare(int num) {
//        int low = 1, high = num;
//        while (low <= high) {
//            long mid = (low + high) >>> 1;
//            if (mid * mid == num) {
//                return true;
//            } else if (mid * mid < num) {
//                low = (int) mid + 1;
//            } else {
//                high = (int) mid - 1;
//            }
//        }
//        return false;
//    }